#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : InsertionSortList.py
# @Time    : 2020/11/20 10:04
# @Description:


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        """
        Sort a linked list using insertion sort.
        Algorithm of Insertion Sort:
            1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
            2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs
            within the sorted list, and inserts it there.
            3. It repeats until no input elements remain.

        Example 1:
            Input: 4->2->1->3
            Output: 1->2->3->4
        Example 2:
            Input: -1->5->3->4->0
            Output: -1->0->3->4->5

        :param head:
        :return:
        """
        if not head:
            return head
        dummy_head = ListNode(0)
        dummy_head.next = head
        last_sorted = head
        curr = head.next

        while curr:
            if last_sorted.val <= curr.val:
                last_sorted = last_sorted.next
            else:
                prev = dummy_head
                while prev.next.val <= curr.val:
                    prev = prev.next
                last_sorted.next = curr.next
                curr.next = prev.next
                prev.next = curr
            curr = last_sorted.next
        return dummy_head.next


if __name__ == '__main__':
    S = Solution()
    head = ListNode(4)
    head.next = ListNode(2)
    head.next.next = ListNode(1)
    head.next.next.next = ListNode(3)
    a = S.insertionSortList(head)
    print('done')
